/*   
* Este programa implementa o algoritmo de Dijkstra para o problema do 
* caminho de custo minimo em grafos dirigidos com custos positivos nas
* arestas.
*/

#include "dijkstra.h"

int destino, origem, vertices = 0;
int custo, *custos = NULL; 

int* dijkstra(int vertices,int origem,int destino,int *custos, int *numero_vertices)
{
	int i,v, cont;
	int *ant;
	int *tmp;  
	int *z;     /* vertices para os quais se conhece o caminho minimo */
	double min;
	double dist[vertices]; /* vetor com os custos dos caminhos */

	/* aloca as linhas da matriz */
	ant = (int *) calloc (vertices, sizeof(int *));
	tmp = (int *) calloc (vertices, sizeof(int *));
	if (ant == NULL) {
		printf ("** Erro: Memoria Insuficiente **");
		exit(-1);
	}

	z = (int *) calloc (vertices, sizeof(int *));
	if (z == NULL) {
		printf ("** Erro: Memoria Insuficiente **");
		exit(-1);
	}

	for (i = 0; i < vertices; i++) {
		if (custos[(origem - 1) * vertices + i] != -1) {
			ant[i] = origem - 1;
			dist[i] = custos[(origem-1)*vertices+i];
		}
		else {
			ant[i]= -1;
			dist[i] = HUGE_VAL;
		}
		z[i]=0;
	}
	z[origem-1] = 1;
	dist[origem-1] = 0;

	int j = 0;
	/* Laco principal */
	do 
	{
		/* Encontrando o vertice que deve entrar em z */
		min = HUGE_VAL;
		for (i=0;i<vertices;i++)
			if (!z[i])
				if (dist[i]>=0 && dist[i]<min) {
					min=dist[i];v=i;
				}

		/* Calculando as distancias dos novos vizinhos de z */
		if (min != HUGE_VAL && v != destino - 1) {
			z[v] = 1;
			for (i = 0; i < vertices; i++)
				if (!z[i]) {
					if (custos[v*vertices+i] != -1 && dist[v] + custos[v*vertices+i] < dist[i]) {
					   	dist[i] = dist[v] + custos[v*vertices+i];
						ant[i] = v;
				   	}
        		}
		}
	} while (v != destino - 1 && min != HUGE_VAL);

	/* Mostra o Resultado da busca */
	printf("\tDe %d para %d: \t", origem, destino);
	if (min == HUGE_VAL) {
		printf("Nao Existe\n");
		printf("\tCusto: \t- \n");
	}
	else {
		i = destino;
		i = ant[i-1];
		tmp[0] = destino;
		cont = 1;
		while (i != -1) {
		//	printf("<-%d",i+1);
			tmp[cont] = i+1;
			cont++;
			i = ant[i];
		}
		
		for (i = cont; i > 0 ; i--) {
			printf("%d -> ", tmp[i-1]);
		}
		
		printf("\n\tCusto:  %d\n",(int) dist[destino-1]);
	}

	*numero_vertices = cont;
	return tmp;
}

int main (int argc, char** argv)
{
	int shmid, n_vertices;
	char* shm, *s;
	key_t key = KEY_SHDMEM;

	// Cria area de memoria compartilhada (create & read-write)
	if ((shmid = shmget(key, sizeof(int)*TAMANHO_CUSTOS*TAMANHO_CUSTOS, 0666)) == -1)
	{
   		perror("shmget");
		exit(-1);
	}

	// Anexa o processo corrente a area recem criada
	if ((shm = (char*) shmat(shmid, NULL, 0)) == (char *) -1) 
	{
        	perror("shmat");
	        exit(-1);
	}

	int i, j;
	int custos[TAMANHO_CUSTOS*TAMANHO_CUSTOS];
	s = shm;
	for(i = 0; i < TAMANHO_CUSTOS; i++)
	{
		for(j = 0; j < TAMANHO_CUSTOS; j++)
			custos[TAMANHO_CUSTOS*i + j] = *s++;
	}

	int *caminho = dijkstra(TAMANHO_CUSTOS, 13, 16, custos, &n_vertices);

	s = shm;	
	for(i = 0; i < n_vertices; i++)
		*s++ = caminho[i];
	*s = n_vertices;
}

